package org.lql.algo.codecrush.week010;

import org.lql.algo.common.TreeNode;

/**
 * @author: liangqinglong
 * @date: 2025-08-30 15:39
 * @description: 106. 从中序与后序遍历序列构造二叉树 <a href="https://leetcode.cn/problems/construct-binary-tree-from-inorder-and-postorder-traversal/description/">...</a>
 **/
public class BuildTree23 {

	private int[] inorder;
	private int[] postorder;

	public TreeNode buildTree(int[] inorder, int[] postorder) {
		if (inorder == null || postorder == null || inorder.length == 0 || postorder.length == 0) {
			return null;
		}
		this.inorder = inorder;
		this.postorder = postorder;
		return build(0, inorder.length - 1, 0, postorder.length - 1);
	}

	private TreeNode build(int inStart, int inEnd, int postStart, int postEnd) {
		// 边界判断
		if (inStart > inEnd || postStart > postEnd) {
			return null;
		}
		// 后续遍历的末位置为根节点
		TreeNode root = new TreeNode(postorder[postEnd]);
		// 中序根节点
		int rootIndex = inStart;
		while (inorder[rootIndex] != root.val) {
			rootIndex++;
		}
		// 左子树大小
		int leftLength = rootIndex - inStart;
		root.left = build(inStart, rootIndex - 1, postStart, postStart + leftLength - 1);
		root.right = build(rootIndex + 1, inEnd, postStart + leftLength, postEnd - 1);
		return root;
	}
}
